package hasWeight;

import java.util.Arrays;

public class Floyed {
    private WeightedGraph g;
    private int[][] dis;
    private boolean hasNegativeCycle = false;

    public Floyed(WeightedGraph g) {
        this.g = g;
        dis = new int[g.getVertexNum()][g.getVertexNum()];
        for (int i = 0; i < g.getVertexNum(); i++) {
            Arrays.fill(dis[i], Integer.MAX_VALUE);
        }
        for (int v = 0; v < g.getVertexNum(); v++) {
            dis[v][v] = 0;
            for (int w : g.adj(v)) {
                dis[v][w] = g.getWeight(v, w);
            }
        }

        for (int t = 0; t < g.getVertexNum(); t++) {
            for (int v = 0; v < g.getVertexNum(); v++) {
                for (int w = 0; w < g.getVertexNum(); w++) {
                    if (dis[v][t] != Integer.MAX_VALUE
                            && dis[t][w] != Integer.MAX_VALUE
                            && dis[v][t] + dis[t][w] < dis[v][w]) {
                        dis[v][w] = dis[v][t] + dis[t][w];
                    }
                }
            }
        }
        for (int v = 0; v < g.getVertexNum(); v++) {
            if (dis[v][v] < 0) {
                hasNegativeCycle = true;
                break;
            }
        }
    }

    public boolean hasNegCycle() {
        return hasNegativeCycle;
    }

    public boolean isConnectedTo(int v, int w) {
        g.validateVertex(v);
        g.validateVertex(w);
        return dis[v][w] != Integer.MAX_VALUE;
    }

    public int disTo(int v, int w) {
        g.validateVertex(v);
        g.validateVertex(w);
        return dis[v][w];
    }

    public static void main(String[] args) {
        WeightedGraph g = new WeightedGraph("bellman.txt");
        Floyed floyed = new Floyed(g);
        if (!floyed.hasNegCycle()) {
            for (int v = 0; v < g.getVertexNum(); v++) {
                for (int w = 0; w < g.getVertexNum(); w++) {
                    System.out.print(floyed.disTo(v, w) + " ");
                }
                System.out.println();
            }
        } else {
            System.out.println("Graph has negative cycle.");
        }
    }
}
